package LimitedTimeGame.Day_0225;

/**
 * @author zxc
 * @date 2023/02/25 09:01
 **/

/**
 * 题目 ：交换字符使得字符串相同
 * 题目详述 ：
 * 有两个长度相同的字符串s1 和s2，且它们其中只含有字符"x" 和"y"，你需要通过「交换字符」的方式使这两个字符串相同。
 * 每次「交换字符」的时候，你都可以在两个字符串中各选一个字符进行交换。
 * 交换只能发生在两个不同的字符串之间，绝对不能发生在同一个字符串内部。
 * 也就是说，我们可以交换s1[i] 和s2[j]，但不能交换s1[i] 和s1[j]。
 * 最后，请你返回使 s1 和 s2 相同的最小交换次数，如果没有方法能够使得这两个字符串相同，则返回-1 。
 *
 * 提示：
 * 1 <= s1.length, s2.length <= 1000
 * s1, s2 只包含 'x' 或 'y'。
 *
 */
public class MinimumSwap {
    /**
     * 思路 ：
     * （1）首先，遍历两个字符串，统计字符串s2中 与字符串s1中对应字符不相同的 x && y总数;
     * （2）最小交换次数 = 不同y的总数/2 + 不同x的总数/2;（若是x和y总数都是奇数的话）
     * （3）最小交换次数 = 不同y的总数/2 + 不同x的总数/2;（若是x和y总数都是偶数的话）
     * @param s1
     * @param s2
     * @return
     */
    public int minimumSwap(String s1, String s2) {
        int len1 = s1.length();
        int len2 = s2.length();
        // 辅助数组用来保存 不同数组对（即，以字符串s2中对应字符进行保存）;
        int[] dp = new int[2];
        if(len1 != len2){
            return -1;
        }
        // 遍历字符串s1和s2，获取其中不同的字符对数量;
        for(int i = 0 ; i < len1 ; i++){
            if(s1.charAt(i) != s2.charAt(i)){
                if(s2.charAt(i) == 'x'){
                    dp[0]++;
                }
                else {
                    dp[1]++;
                }
            }
        }
        // 若是不相同的字符对是奇数的话，则不能够交换得到相同字符串;
        if((dp[0] + dp[1]) % 2 == 1){
            return -1;
        }
        int result = 0;
        // 若是存在([y,x] , [y,x]) || (([x,y] , [x,y]))的话，只需要交换一次即可实现;
        result = dp[0] / 2 + dp[1] / 2;
        dp[0] %= 2;
        dp[1] %= 2;
        // 若是剩余 [x,y] && [y,x]的话，则需要进行两次交换才可以实现;
        if(dp[1] == 1 && dp[0] == 1){
            result += 2;
        }
        return result;
    }
}
